package com.le.tester.imooc.oldfairy.coding.sorting;

import org.junit.Test;

/**
 * createTime：2023/5/23 9:29
 * description：插入排序
 */
public class InsertionSort implements IMutableSorter {


    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            //标记当前的数值
            int currNum = arr[i];
            //新牌暂时存放的位置
            int j = i;
            //有两个值且新的值大于当前的数值才进行排序，前面的值如果是比较大的，放到当前即可
            for (; j > 0 && arr[j - 1] > currNum; j--) {
                //大的值放前
                arr[j] = arr[j - 1];
            }
            //小的值放后
            arr[j] = currNum;
        }
    }


    @Test
    public void TestInsertSort() {
        this.sort(new int[]{1, 2, 3, 5, 4, 8, 9, 256, 7, 8, 9});
    }
}
